package question

//1091. 二进制矩阵中的最短路径
func shortestPathBinaryMatrix(grid [][]int) int {
	if grid[0][0] == 1 {
		return -1
	}
	m := len(grid)
	n := len(grid[0])
	queue := [][2]int{{0, 0}}
	ans := 1
	for len(queue) > 0 {
		k := len(queue)
		for i := 0; i < k; i++ {
			p := queue[i]
			x, y := p[0], p[1]
			if x == m-1 && y == n-1 {
				return ans
			}
			if x-1 >= 0 && y-1 >= 0 && grid[x-1][y-1] == 0 {
				queue = append(queue, [2]int{x - 1, y - 1})
				grid[x-1][y-1] = 1
			}
			if x-1 >= 0 && grid[x-1][y] == 0 {
				queue = append(queue, [2]int{x - 1, y})
				grid[x-1][y] = 1
			}
			if x-1 >= 0 && y+1 < n && grid[x-1][y+1] == 0 {
				queue = append(queue, [2]int{x - 1, y + 1})
				grid[x-1][y+1] = 1
			}
			if y+1 < n && grid[x][y+1] == 0 {
				queue = append(queue, [2]int{x, y + 1})
				grid[x][y+1] = 1
			}
			if x+1 < m && y+1 < n && grid[x+1][y+1] == 0 {
				queue = append(queue, [2]int{x + 1, y + 1})
				grid[x+1][y+1] = 1
			}
			if x+1 < m && grid[x+1][y] == 0 {
				queue = append(queue, [2]int{x + 1, y})
				grid[x+1][y] = 1
			}
			if x+1 < m && y-1 >= 0 && grid[x+1][y-1] == 0 {
				queue = append(queue, [2]int{x + 1, y - 1})
				grid[x+1][y-1] = 1
			}
			if y-1 >= 0 && grid[x][y-1] == 0 {
				queue = append(queue, [2]int{x, y - 1})
				grid[x][y-1] = 1
			}
		}
		ans++
		queue = queue[1:]
	}

	return -1

	//超时了
	/* min := -1
	m := len(grid)
	if m == 0 {
		return min
	}
	n := len(grid[0])
	if n == 0 {
		return min
	}

	var dfs func(i, j, count int)
	dfs = func(i, j, count int) {
		if i == -1 || i == m || j == -1 || j == n {
			return
		}
		if grid[i][j] == 1 {
			return
		}
		count += 1
		grid[i][j] = 1
		if i == m-1 && j == n-1 {
			if min == -1 || min > count {
				min = count
			}
		} else {
			//左上
			dfs(i-1, j-1, count)
			//上
			dfs(i-1, j, count)
			//右上
			dfs(i-1, j+1, count)
			//右
			dfs(i, j+1, count)
			//右下
			dfs(i+1, j+1, count)
			//下
			dfs(i+1, j, count)
			//左下
			dfs(i+1, j-1, count)
			//左
			dfs(i, j-1, count)
		}
		grid[i][j] = 0
	}

	dfs(0, 0, 0)
	return min */
}
